Enumerate and Measure: Improving Parameter Budget Management
Identifieur interne : 000C40 ( Main/Exploration ); précédent : 000C39; suivant : 000C41Enumerate and Measure: Improving Parameter Budget Management
Auteurs : Daniel Binkele-Raible [Allemagne] ; Henning Fernau [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.
Abstract
Abstract: Measure & Conquer (M&C) is the prominent technique for analyzing exact algorithms for computationally hard problems . It tries to balance worse and better situations within the algorithm analysis. Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to Vertex Cover, namely Connected Vertex Cover and Edge Dominating Set. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers and then producing solutions to the requested problem. Using M&C in this context will improve on the hitherto published running times, offering some unifying view. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.
Url:
DOI: 10.1007/978-3-642-17493-3_6
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001A62
- to stream Istex, to step Curation: 001945
- to stream Istex, to step Checkpoint: 000319
- to stream Main, to step Merge: 000C94
- to stream Main, to step Curation: 000C40
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Enumerate and Measure: Improving Parameter Budget Management</title><author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:91DD40A8DDC779C446188605628AFD7C1FFDA200</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-17493-3_6</idno><idno type="url">https://api.istex.fr/document/91DD40A8DDC779C446188605628AFD7C1FFDA200/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A62</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A62</idno><idno type="wicri:Area/Istex/Curation">001945</idno><idno type="wicri:Area/Istex/Checkpoint">000319</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000319</idno><idno type="wicri:doubleKey">0302-9743:2010:Binkele Raible D:enumerate:and:measure</idno><idno type="wicri:Area/Main/Merge">000C94</idno><idno type="wicri:Area/Main/Curation">000C40</idno><idno type="wicri:Area/Main/Exploration">000C40</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Enumerate and Measure: Improving Parameter Budget Management</title><author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2010</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">91DD40A8DDC779C446188605628AFD7C1FFDA200</idno><idno type="DOI">10.1007/978-3-642-17493-3_6</idno><idno type="ChapterID">6</idno><idno type="ChapterID">Chap6</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Measure & Conquer (M&C) is the prominent technique for analyzing exact algorithms for computationally hard problems . It tries to balance worse and better situations within the algorithm analysis. Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to Vertex Cover, namely Connected Vertex Cover and Edge Dominating Set. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers and then producing solutions to the requested problem. Using M&C in this context will improve on the hitherto published running times, offering some unifying view. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><noRegion><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name></noRegion><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C40 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000C40 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:91DD40A8DDC779C446188605628AFD7C1FFDA200
|texte= Enumerate and Measure: Improving Parameter Budget Management
}}
| This area was generated with Dilib version V0.6.31. |  |